//金明的预算方案
#include <iostream>
using namespace std;
const int MAXN=32000;
const int MAXM=60;
int n,m;
int v[MAXM+1],p[MAXM+1],q[MAXM+1];
int accnum[MAXM+1],access[MAXM+1][3];
int maxvp[MAXN+1];

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>v[i]>>p[i]>>q[i];
        if (q[i]>0){
            access[q[i]][accnum[q[i]]++]=i;
        }
    }

    for(int i=1;i<=m;i++)
        if (q[i]==0)
            for(int n1=n;n1>=v[i];n1--){
                if (maxvp[n1]<maxvp[n1-v[i]]+v[i]*p[i]) maxvp[n1]=maxvp[n1-v[i]]+v[i]*p[i];
                for(int k=0;k<accnum[i];k++){
                    int newv=v[i]+v[access[i][k]];
                    int newvp=v[i]*p[i]+v[access[i][k]]*p[access[i][k]];
                    if (n1>=newv&&maxvp[n1]<maxvp[n1-newv]+newvp) maxvp[n1]=maxvp[n1-newv]+newvp;
                }
                if (accnum[i]==2){
                    int newv=v[i]+v[access[i][0]]+v[access[i][1]];
                    int newvp=v[i]*p[i]+v[access[i][0]]*p[access[i][0]]+v[access[i][1]]*p[access[i][1]];
                    if (n1>=newv&&maxvp[n1]<maxvp[n1-newv]+newvp) maxvp[n1]=maxvp[n1-newv]+newvp;
                }
            }
    cout<<maxvp[n];
}